package P912.P51;

import org.junit.Test;

/**
 * @Author DJ同学
 * @Date 2021/2/28 19:22
 * @Version 1.0
 * @Name 数组中的逆序对
 * @Problem https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
 * 主要是 三部分 左边的逆序对+右边逆序对+合并的逆序对
 */
public class Solution {

    @Test
    public void test(){
        int i = reversePairs(new int[]{7,5,6,4});
        System.out.println(i);
    }

    int[] nums,temp;
    public int reversePairs(int[] nums) {
        if(nums==null||nums.length==0){
            return 0;
        }
        this.nums = nums;
        temp = new int[nums.length];
        return sort(0,nums.length);
    }
    int sort(int left,int right){
        if(left+1==right){
            //System.out.println("["+left+","+right+"]"+":0");
            return 0;
        }
        int mid = left+((right-left)>>1);
        //左右两边的逆序数
        int res = sort(left,mid)+sort(mid,right);
        if(nums[mid-1]<nums[mid]){
            //System.out.println("["+left+","+right+"]"+":"+res);
            return res;
        }
        //合并
        res+=merge(left,mid,right);
        //System.out.println("["+left+","+right+"]"+":"+res);
        return res;
    }

    int merge(int left,int mid,int right){
        //[left,mid) [mid,right)
        int k = 0;
        int i = left;
        int j = mid;
        int cnt = 0;
        while(i<mid&&j<right){
            if(nums[i]<=nums[j]){
                temp[k++]=nums[i++];
            }else{
                //第一个数组i包括，i后面的数都可以匹配第二个数组的当前值
                //以第一个数组为核心 不能是cnt+=j-mid+1,这样会加重复了
                cnt += mid-i;
                temp[k++]=nums[j++];
                //出现逆序数
            }
        }
        while(i<mid){
            temp[k++]=nums[i++];
        }
        while(j<right){
            temp[k++]=nums[j++];
        }
        for(int l = 0;l<k;l++){
            nums[left+l]=temp[l];
        }
        return cnt;
    }
}
